package leetcode

/*
 * @lc app=leetcode.cn id=316 lang=golang
 *
 * [316] 去除重复字母
 */

// @lc code=start
func removeDuplicateLetters2(s string) string {
	rest := make(map[rune]int, 26)
	for _, ch := range s {
		if _, ok := rest[ch]; ok {
			rest[ch]++
		} else {
			rest[ch] = 1
		}
	}
	got := make(map[rune]struct{}, 26)
	ret := make([]rune, 0, 26)
	for _, ch := range s {
		if _, ok := got[ch]; !ok {
			for len(ret) != 0 &&
				ret[len(ret)-1] > ch &&
				rest[ret[len(ret)-1]] > 0 {
				delete(got, ret[len(ret)-1])
				ret = ret[:len(ret)-1]
			}
			got[ch] = struct{}{}
			ret = append(ret, ch)
		}
		rest[ch]--
	}
	return string(ret)
}

func removeDuplicateLetters(s string) string {
	left := [26]int{}
	for _, ch := range s {
		left[ch-'a']++
	}
	stack := make([]rune, 0, 26)
	inStack := [26]bool{}
	for _, ch := range s {
		if !inStack[ch-'a'] {
			for len(stack) > 0 &&
				stack[len(stack)-1] > ch &&
				left[stack[len(stack)-1]-'a'] > 0 {
				inStack[stack[len(stack)-1]-'a'] = false
				stack = stack[:len(stack)-1]
			}
			stack = append(stack, ch)
			inStack[ch-'a'] = true
		}
		left[ch-'a']--
	}
	return string(stack)
}

// @lc code=end
